This paper uses the dynamic network G to model the process of evolution of the Internet over time. The relevant definitions are given below, and a glossary of terms and abbreviations used are given in Table 1.

Table 1.

Table 1.

Table 1. Glossary and abbreviation. . Symbol Description g(i) A network topology snapshot at time tick i G All network topology snapshots N The number of network nodes E The number of network edges t(i) The time at tick i Nsteady The set of steady nodes Ndead The set of dead nodes Nborn The set of born nodes The set of dead edges in the internal area The set of dead edges in the boundary area The set of dead edges in the external area The set of born edges in the internal area The set of born edges in the boundary area The set of born edges in the external area The set of steady edges M1 A component as shown in Fig. 2(a) M2 A component as shown in Fig. 2(b) M3 A component as shown in Fig. 2(c)

Table 1. Glossary and abbreviation. .

Dynamic network: a dynamic network G is a set of networks: , where i is the time index, T is the total number of time slots, g(i) is the sampled network at time i, and N(i) and E(i) are the nodes set and the edges set of g(i). Every node connects with at least one other node in the static network, unless the static network consists of one node only.

Steady node: for a node n ∈ N(i), if n ∈ N(i + 1), then n is considered as a steady node during [i,i + 1]. All steady nodes comprise the steady nodes set: N_steady (i, i + 1) = N(i) ∩ N(i + 1), which are nodes {E, H, G, F, I} in Fig. 1.

Fig. 1.

Figure Option ViewDownloadNew Window

Fig. 1. (color online) Schematic diagram of network evolution from t(i) to t(i + 1). The two shades g(i) and g(i + 1) refer to the topology snapshot at time i and i + 1, respectively. The overlap of both shades denotes the area that remains unchanged from t(i) to t(i + 1), covering the steady nodes {E, H, G, F, I} and edges. The purple shade on the left contains the vanishing nodes {A, B, C, D} and edges { , , }, whereas the yellow shade on the right contains the new born nodes {J, K, L, M} and edges { , , .

Dead node: for a node n ∈ N(i), if n does not belong to N(i + 1), then n is considered as a dead node during [i, i + 1]. All dead nodes comprise the dead nodes set:

Newborn node: for a node n ∈ N(i + 1), but n does not belong to N(i), then n is considered as a newborn node during [i, i + 1]. All newborn nodes comprise the newborn nodes set:

Dynamic nodes: all dead nodes and newborn nodes are considered as dynamic nodes.

Internal edge, boundary edge, and external edge: for an edge, if its two vertices are both steady nodes, then it is considered as an internal edge, such as {E–G, F–G, G–H, G–I, E–F, E–H, H–I} if its two vertices are both dynamic nodes, then it is considered as an external edge, such as {A–C, B–C, J–K, J–L}; otherwise it is considered as a boundary edge, such as {C–E, D–F, H–M, I–J}.

Dead edge: for an edge, if it belongs to E(i) but does not belong to E(i + 1), then it is considered as a dead edge.

Newborn edge: for an edge, if it belongs to E(i + 1) but does not belong to E(i), then it is considered as a born edge.

In some studies, the new-born nodes and dead nodes of the Internet IP-level network are treated equally, without considering the fact that some elements work together as one unit.^[28,29] These cooperating elements contain up to three nodes, which are the most basic and fundamental elements after one singular node, so that each component consists of only two or three nodes and a few edges. A diagram of these three basic components (M1, M2, and M3) is shown in Fig. 2. The individual components can be defined as:

Fig. 2.

	Figure Option ViewDownloadNew Window
	Fig. 2. Graphs of 3 simple components in complex networks. (a) Single-edge component M1; (b) Binary component M2, with three nodes and two edges; (c) The triangle component M3.

M1: the most basic component, which consists of two nodes and one edge. If this edge is a newborn internal edge, this subgraph is considered as an internal-born-M1 component, . , , , , are defined similarly.

M2: a network consists of three nodes and two edges. If both edges are new born internal edges, then it is considered as an internal-born-M2 component, . , , are defined similarly. If at least one of the two edges is a new born boundary edge, then it is considered as a boundary-born-M2 component . is defined similarly.

M3: a network consists of three fully connected nodes. If all three edges are new born internal edges, then it is considered as an internal-born-M3 component, . , , are defined similarly. If at least one of the three edges is a new born boundary edge, then it is considered as a boundary-born-M3 component . is defined similarly.

Researchers have modified a few entropy change formulas in various interdisciplinary applications.^[30–33] To observe the system structure state during the evolution of the Internet, we selected one which depicts topological feature. The structural entropy of complex network was defined as in Eq. (1).^[33]

Communication networks, social networks, power grids, protein–protein interaction networks and neural networks can all be considered as complex networks consisting of a series of nodes and edges, on which signals and information can be transmitted from the source nodes to the target nodes by specific routing rules. The global topology of a complex network can influence the local information flow direction and the nodes’ load. Local changes can cause system fluctuation and lead to large scale network crashes due to a cascading failure reaction.

For example, with the development of the Internet, nodes and edges in the Internet have increased significantly. Figures 3(a) and 3(b) show numbers of nodes and edges of the Internet from January 1998 to August 2013, and piecewise regressions are used to reflect the trends of the growths of nodes and edges. In Fig. 3(a), according to the distribution of the number of nodes vs date, in the range of January 1998 to July 2001, as well as in the range of January 2003 to August 2013, an exponential regression model and a linear regression model are used to fit the data, respectively. This regression model is described by (where x is the number of days from January 1998, and y is the number of nodes):

Fig. 3.

Figure Option ViewDownloadNew Window

Fig. 3. (color online) Growth of nodes and edges of the AS-level Internet from January (Jan) 1998 to August (Aug) 2013. (a) Increase of the Internet nodes over time. (b) Increase of the Internet edges over time. (c)–(f) Comparisons of the dead (red dots) and born (blue dots) elements of the Internet network topology from January 1998 to August 2013, in which dead elements are represented by red dots and born elements are represented by blue ones. (c) The Internet nodes, Ndead and Nborn; (d) Internal edges of the Internet, and ; (e) Boundary edges of the Internet, and ; (f) External edges of the Internet, and .

y = 2411.35* e^x/25.34 + 631.75, where x is in the range of January 1998 to July 2003;

y = −92.43+244.89*. x, where x is in the range of January 2003 to August 2013.

In Fig. 3(b), according to the distribution of the number of edges vs. date, in the range of January 1998 to July 2001, as well as in the range of July 2001 to August 2013, one exponential regression model and a polynomial regression model are used. This regression model is described by (where x is the number of days from January 1998, and y is the number of edges):

y = 5099.52* e^x/24.06 + 181.44, where x is in the range of January 1998 to July 2001;

y = 3.57* x² + 18.93* x + 22190.24, where x is in the range of July 2001 to August 2013.

The regression models show the Internet global progress from a very simple topology with a few nodes and edges in 1998 to a fairly complicated topology with an enormous number of nodes and edges in 2013, they briefly show the trend of developments of nodes and edges of the Internet topology. The number of nodes and edges of the Internet have been increasing continuously (Figs. 3(a) and 3(b)), with nodes of the Internet’s topology emerging and vanishing simultaneously. The y axises show the measures of the number of nodes and edges, where are 0 to 5 × 10⁴ and 0 to 1.8 × 10⁵, respectively (Figs. 3(a) and 3(b)), which imply the growth of network edges outpaces the growth of network nodes. Given that the network topology is adding and removing nodes constantly, each node change will have a follow-up effect. Like the butterfly effect, a small change at one place in a complex system can have large effects elsewhere. With these simulation models, we make an effort to give a brief estimation, or a prediction, that this trend of the Internet will progress in the near future.

We investigated the process of evolution of the birth and dead activities separately (Fig. 3(c) to Fig. 3(f)). Figure 3(c) gives the numbers of newborn nodes and dead nodes, whereas Figs. 3(d), 3(e), and 3(f) demonstrate the numbers of newborn and dead internal-edges, boundary-edges, and external-edges, respectively. In each time slot, the number of born nodes is always greater than that of dead ones (Fig. 3(c)). The amount of the newborn nodes and dead nodes evolve synchronously.

The internal-edges (E^internal) mainly take part in the local restructuring to make the Internet not only meet the requirement of system growth but also improve system robustness. The proportion of E^internal is about 90%. These edges participate in the Internet evolutionary process whenever necessary. They are formed by the nodes which select better neighbors for themselves by optimizing the connections. The boundary-edges (E^boundary) ensure that every newborn node can be part of the Internet in time and that dead nodes are removed from the Internet topology effectively. The proportion of these edges is about 9%. Only about 1% of the edges are external-edges (E^external). They are removed from the network topology together with the related endpoints. This implies that there are interdependencies in between these two newborn nodes or dead nodes, and none are discrete individuals. The internal-edges dominate the dynamical growth of the Internet (Fig. 3) in the sense of the activities of birth or death of nodes and their correlated edges. Here, trends of and were fitted to exponential regression models, and it was found that the number of newborn and dead edges can be described by: y_born = 712.34* e^x/79.97 + 253.41 and y_dead = 1064.67* e^x/103.65 − 390.44, respectively.

To observe the overall growth of the network edges, an estimate of the mean birth rate is described by:

According to these results and the general principle of networking, an Internet evolution scenario is described as a newborn node usually builds connections (boundary edges) with one or more than one existing nodes first to join into the Internet system. Furthermore, some nodes are interconnected by external-edges which are added to the Internet at the same time. They then participate in the local restructuring activities by adjusting local connections. Although the nodes and edges are the basic elements of the complex network, the network components representing the function structures are more relevant to study the complex behaviors of the Internet’s evolution. Therefore, in the next section, we will investigate the evolution of network components.

The internal-edges are the main factors governing the evolution of the Internet, while the effect of the two other types of edges is marginal. Therefore, whether the internal-edges will cooperate with other types of edges to co-build a network is of interest, such as by sharing common nodes. In other words, might the internal-edges participate to form any network components, while the boundary edges and external edges form the network components dynamically? How do those network topology components evolve? A router cannot establish the connections with an unlimited number of routers instantly and the old Internet architecture cannot adapt to the modern technology. Therefore, network administrators have to change the old Internet architecture or the local network connections to improve the Internet’s efficiency. This is a scenario of network component reconstruction, and the reality becomes even more complicated. This study simplified these complicated scenarios into the following procedure: Any changes within the network, either addition or removal of nodes, edges or components, will break the system’s equilibrium. However, the system itself will strive to maintain equilibrium by adding or removing some certain elements. Our work investigated three particular types of network component, M1, M2, and M3; as shown in Fig. 2.

Table 2 demonstrates the evolution of components M1, M2, and M3 from 1998 to 2013 by showing the numbers of born and dead components of 16 sampled topologies of the Internet. It can be found that the internal components play a major role in the evolution of the Internet. This phenomenon of evolution is more obvious among internal components than among boundary components and external components. From Table 2 it can be seen that the number of the external-components is lower than the number of the internal-components and the boundary-components. This can be concluded from the fact that the number of the external-edges is lower than the number of both the internal-edges and the boundary-edges (Fig. 3(d)–Fig. 3(f)). Second, according to Table 2, component M3 appears to be absent from boundary-components and external-components. Third, the number of newborn M2 components is greater than that of born M1, while the number of dead components M2 is similar to that of dead M1s. This indicates that the newborn node prefers to build up connections with at least three nodes and that the dead nodes are the leaf nodes of the network. It also verifies the notion that the number of connections of a node is positively related to the robustness of a node.^[28] Referring to internal-components, which are composed of internal edges, component M2 is the main contributor to the dynamical structure of internal-components, which accounts for 95% ∼ 97% (Table 2), and the number of M3 is the lowest contributor ( ca. 1.04%). These results indicate that component M2 is more important than the other components in the process of the Internet’s evolution. This result also confirms the observation that the Internet consists mainly of star-like or tree-like structures. In other words, a node prefers to get started by connecting with multi-nodes to form an M2 component in order to take part in the network topology. Afterwards, an M2 component connects to other M2s to form a tree. The network keeps replicating M2s and connecting them together continuously. As for M3, the particular triangle shape could supply more stability to its own and also to the whole topology. Therefore, the stability of the Internet is positively related to the number of M3 components that it contains. The network components’ reconstruction is completed by the activities of the edges. Since edge evolution is the process of system optimization, it can be suggested that components reconstruction also participates in the main process of system optimization.

So far in this study, the Internet’s activities are analyzed from the node level, the edge level, and the component level. During the evolution of the Internet, the whole topology structure adds new nodes, whilst components are formed to reconstruct the system topology. Table shows that components are added into and removed from the Internet at the same time to keep the system equilibrium. For example, both the birth and death of elements can cause the system to diverge from equilibrium. The system reacts as a self-organizing system^[25] to maintain the equilibrium, by adding or removing certain elements. Although it is impossible to distinguish whether birth will precede death, is there a correlation between components’ births and deaths? To answer this question, the details of the Internet reconstruction are studied as follows.

Table 2.

Table 2.

Table 2. The evolution activities of network components M1, M2, and M3. . Sample period Birth Death Internal Boundary External Internal Boundary External M1 M2 M3 M1 M2 M3 M1 M2 M3 M1 M2 M3 M1 M2 M3 M1 M2 M3 01 Feb. 98-01 Mar. 98 268 1240 0 202 1272 0 10 0 0 253 860 0 80 98 0 0 0 0 01 Feb. 99-01 Mar. 99 423 1980 6 251 1636 0 6 0 0 343 1238 0 57 112 0 0 0 0 01 Feb. 00-01 Mar. 00 733 34952 306 350 3658 0 4 0 0 561 15286 156 117 168 0 0 0 0 01 Feb. 01-01 Mar. 01 1170 64744 846 597 19766 0 12 0 0 921 14122 132 166 642 0 4 0 0 01 Feb. 02-01 Mar. 02 1198 20794 108 440 6260 0 10 0 0 1038 18172 108 229 1546 0 6 0 0 01 Feb. 03-01 Mar. 03 1286 36086 240 379 3748 0 6 0 0 1127 76520 900 180 470 0 2 0 0 01 Feb. 04-01 Mar. 04 1826 531222 29328 559 5652 0 23 20 0 1088 53330 222 170 476 0 0 0 0 01 Feb. 05-01 Mar. 05 1380 59250 330 396 1902 0 4 0 0 1363 36546 330 255 1008 0 0 0 0 01 Feb. 06-01 Mar. 06 1447 113216 1458 464 2298 0 6 0 0 1336 32308 192 211 468 0 4 0 0 01 Feb. 07-01 Mar. 07 1836 94338 990 504 4570 0 7 22 0 1614 22274 102 257 412 0 2 0 0 01 Feb. 08-01 Mar. 08 2226 123778 1794 649 2338 0 4 0 0 1632 94996 1362 183 354 0 2 0 0 01 Feb. 09-01 Mar. 09 2248 303998 2742 616 2628 0 8 2 0 1752 226644 3462 158 252 0 2 0 0 01 Feb. 10-01 Mar. 10 2023 510972 9090 631 2572 0 0 0 0 1897 352470 3828 339 1238 0 13 6 0 01 Feb. 11-01 Mar. 11 2297 585482 6456 764 2732 0 3 6 0 2200 88306 2346 331 482 0 6 2 0 01 Feb. 12-01 Mar. 12 2582 340956 4266 746 1978 0 6 0 0 2323 215892 672 295 608 0 2 2 0 01 Feb. 13-01 Mar. 13 2731 392744 3492 742 1930 0 6 0 0 2425 2755530 59280 391 912 0 7 20 0

Table 2. The evolution activities of network components M1, M2, and M3. .

To address this problem, an analogy is put forward to depict the process of evolution from a single node. One newborn node is like an infant growing up and making friends with other nodes over time, encountering some anomalies and being restrained by the surroundings. In this process, the system allows its participants to involve in the topology by using materials that already exist. A few of these new nodes may disappear after a short time but most of them will continuously participate in the “life-sustaining” process (which can also be called metabolism) within the network’s topology. In this process, some of them even become important or fundamental members (nodes) of the network. Inspired by this analogy, we observed and analyzed the evolutionary process of node AS7713 (AS7713 represents the autonomous system number of a single administrative entity or domain whose information is registered in the RIR). Once AS7713 was added into the Internet in January 1998, its degree grew exponentially after October 2004 (Fig. 4(b)). This indicates that a new born node adapted to the system environment for some time, and then quickly grew to become an important node (according to the case of AS7713). Figure 4(a) is a visualization of a local network including AS7713 and its neighbors in a snapshot network of the on August 2013.

Fig. 4.

Figure Option ViewDownloadNew Window

Fig. 4. (color online) A case of the evolution of node AS7713. (a) AS7713 emerges into the Internet in August 1998 and starts to build connections with its neighbors. The visualization shows a snapshot of the local network topology of AS7713 and its neighbors (August 2013). The colour and size of the nodes vary by node’s degree, the bigger the node is, the lighter the colour is, and the higher degree it has, (b) the degree of AS7713 evolves since a newborn node to an important hub of the Internet.

In Subsection 5.1, we argued that the internal-edges are fundamental elements determining both the Internet network topology and its process of evolution, whereas the boundary-edges are used to receive the born elements or remove the dead elements. AS7713 was added into the Internet by building up boundary edges with those existing nodes first. By continuously establishing connections with its neighbors, it eventually became a hub in the Internet: a node with a greatly above average number of links. In addition, to describe AS7713’s growth, the associated component of the evolutionary process is also analyzed to demonstrate the relationship between the born component and dead component.

Figure 5 contains three cases of reconstruction of internal-edge in the local subnetwork of AS7713 from 2010 to 2012, where the edges are categorized into three types: steady edges, born edges and dead edges. In Fig. 5(a), M2 component ({AS6939–AS38202, AS38202–AS4844} {AS6939–AS38202, AS38202–AS4826}, and {AS4844–AS38202, AS38202–AS4826}) are removed from the network, whilst M3 component ({AS55658–AS4844, AS4844–AS4826, AS4826–AS55658}) is added. This allows AS7713 access to AS4844 and AS4826 via AS55658, despite the disappearance of the connections of AS38202–AS4844 and AS38202–AS4826. According to Fig. 5(b), the local subnetwork turns from component ({AS23947–AS9304, AS23947–AS45896}) to component ({AS23947–AS55658, AS23947–AS18351}). However, in Fig. 5(c), the AS4844–AS2411 is removed while one M1 and one M2 are introduced into the network. The first case shows that the changes improve the network robustness because of the stability of M3. The second case shows the changes of the connection preference. The third case shows that the changes enhance the network connectivity by applying more internal edges.

Fig. 5.

	Figure Option ViewDownloadNew Window
	Fig. 5. (color online) Three Illustrations of network component reconstruction.

The equilibrium of the Internet can be disturbed by either the growth of nodes and edges, or reconstruction of the network components. As a complex system, changes of network nodes, edges, and components are the essential activities of the Internet. We wondered if those essential behaviors will change the basic characteristics of the Internet system. Therefore, we attempted to investigate it from the view of global Internet topology. The Internet is a typical complex network with scale-free characteristics,^[8] where the degree distribution follows the power law, p(k) ∼ k^γ (k is the degree of the nodes in the network. For scale-free network, the γ value is typically in the range [2, 3], although it may occasionally lie outside these bounds, in a number of real world networks it has values between 1.2, 2.9). Power-law values γ of degree distributions of all the sampled networks are in the range [1.78, 2.25] and the standard deviation is 0.13. The degree distribution of the AS-level Internet network appears to follow a power law. The scale-free features of the network are relatively stable, which refers to the growth process and attachment preference have not been changing much over time.

Figure 6 shows the evolution of the structural entropy of the Internet (H) from 1998 to 2013. According to the trend of the structural entropy over time, we can divide this period into two stages: structural entropy decreasing linearly from 0.205 to 0.175 and undulating within the range of [0.1725, 0.180]. From January 1998 to March 2003, the value of the structural entropy mainly decreased linearly along with some fluctuations, which mainly happened between November 2000 to July 2001. The result shows that the Internet tends towards lower structural entropy over time, and with the evolution of the Internet, the topology is becoming more organized, meaning the Internet becomes less random. This follows the general principle of evolution (i.e., evolution in the extended sense is the increase of biological organization, and an irreversible process occurring in time), resulting in an increase of diversity and level of organization in its products.^[37,38]

Fig. 6.

	Figure Option ViewDownloadNew Window
	Fig. 6. The evolution of the structural entropy of the AS-level Internet from 1998 to 2013. From January 1998 to March 2003, the structural entropy of the Internet declined linearly. Afterwards, it mainly fluctuated in the range of [0.1725, 0.180].

From April 2003 to August 2013, the value of H of the Internet remained within the range of [0.1725, 0.180]. The tendency of the fluctuation is slow and smooth. It is worth noting that from 2000 to 2003, the Internet experienced a historic speculative bubble when the stock markets in industrialized countries saw their equity value rise rapidly due to growth in the Internet sectors and related fields.^[39] Before 2003, the Internet Service Providers (ISPs) expanded the Internet infrastructure tremendously to meet the massive needs of Internet companies. After the Internet bubble, the Internet’s resources were in excess because a large number of Internet companies went bankrupt. To decrease the operating costs and to improve the efficiency of network transmission, some ISP companies chose to merge with each other, while other companies optimized their self-network topology to provide better network services. No matter which strategy was chosen, the companies could not change the fact that the Internet topology had made a response to the surrounding environment. The Internet structural entropy decreased linearly from January 1998 to March 2003 (Fig. 6). This procedure is also the process of a rational development for commercial Internet. The Internet’s status then entered a fluctuating phase, which implies that the AS-level Internet architecture and also the level of the randomness of the network topology did not change much after the development (from January 1998 to March 2003).